package com.xinxin.leetcode.problem687;

import com.xinxin.leetcode.common.CommonUtil;
import com.xinxin.leetcode.common.TreeNode;
import com.xinxin.leetcode.common.TreeUtil;

/**
 * @author ShiXinXin
 * @date 2020-02-23 22:40
 */
class Solution {
    private int maxL = 0;

    public int longestUnivaluePath(TreeNode root) {
        if (root == null) {
            return 0;
        }
        getMaxL(root, root.val);
        return maxL;
    }

    private int getMaxL(TreeNode r, int val) {
        if (r == null) {
            return 0;
        }
        int left = getMaxL(r.left, r.val);
        int right = getMaxL(r.right, r.val);
        maxL = Math.max(maxL, left + right);
        if (r.val == val) {
            return Math.max(left, right) + 1;
        }
        return 0;
    }

    public static void main(String[] args) {
        TreeNode root = TreeUtil.createTree(CommonUtil.createArr(5, 4, 1, 0, 0, 1, 0, 0, 5, 0, 5, 0, 0));
        System.out.println(new Solution().longestUnivaluePath(root));
    }
}
